#include <stdio.h>
#include <stdlib.h>
#include "LinkList.h"
#define false 0
#define true 1

void InitLinkList(LinkList *list)
{
    list->len=0;
    list->head=NULL;
}

Node* CreatNode()
{
    Node *newnode=(Node*)malloc(sizeof(Node));
    newnode->next=NULL;
    return newnode;
}

int InsertTail(LinkList *list, Node_ElementType element)
{
    Node* newnode=CreatNode();
    if(newnode==NULL)
    {
        printf("Node malloc error!\n");
        return false;
    }
    newnode->data=element;
    Node* TravelPoint=list->head;
    if(TravelPoint==NULL)
    {
        list->head=newnode;
        list->len++;
    }
    else
    {
        while(TravelPoint->next!=NULL)
        {
            TravelPoint=TravelPoint->next; 
        }
        TravelPoint->next=newnode;
        list->len++;
    }
    return true;
}

int InsertHead(LinkList *list, Node_ElementType element)
{
    Node* newnode=CreatNode();
    if(newnode==NULL)
    {
        printf("Node malloc error!\n");
        return false;
    }
    newnode->data=element;
    newnode->next=list->head;
    list->head=newnode;
    list->len++;
    return true;
}

int InsertIndex(LinkList *list, Node_ElementType element, int index)
{
    if(index<0||index>list->len)
    {
        printf("insert invaild place!\n");
        return false;
    }
    Node* newnode=CreatNode();
    if(newnode==NULL)
    {
        printf("Node malloc error!\n");
        return false;
    }
    newnode->data=element;
    int count=0;
    Node *TravelPoint=list->head;
    if(index==0)
    {
        newnode->next=TravelPoint;
        list->head=newnode;
    }
    else
    {
        while(count<index-1)
        {
            TravelPoint=TravelPoint->next;
            count++;
        }
        newnode->next=TravelPoint->next;
        TravelPoint->next=newnode;
    }
    list->len++;
    return true;
}

void RemoveByindex(LinkList *list, int index)
{
    if(index<0||index>=list->len)
    {
        printf("remove invaild place!\n");
        return ;
    }
    Node *Travelpoint=list->head;
    int count=0;
    while(count<index-1)
    {
        Travelpoint=Travelpoint->next;
        count++;   
    }
    Node *FreeNode=Travelpoint->next;
    Travelpoint->next=Travelpoint->next->next;
    list->len--;
    free(FreeNode);
}

void RemoveIByElement(LinkList *list, Node_ElementType element)
{
    if(list->len==0)
        return;
    Node *TravelPoint=list->head;
    Node *NextNode;
    
    while(TravelPoint->next!=NULL)
    {
        if(TravelPoint->next->data==element)
        {
            NextNode=TravelPoint->next;
            TravelPoint->next=TravelPoint->next->next;
            free(NextNode);
            list->len--;
        }
        else
            TravelPoint=TravelPoint->next;
    }
    if(list->head->data==element)
    {
        NextNode=list->head;
        list->head=list->head->next;
        free(NextNode);
        list->len--;
    }
}

Node_ElementType *FindByIndex(LinkList *list, int index)
{
    if(index<0||index>=list->len)
    {
        printf("find invaild place!\n");
        return NULL;
    }
    Node *TravelPoint=list->head;
    int count=0;
    while(count<index)
    {   
        count++;
        TravelPoint=TravelPoint->next;
    }
    return &TravelPoint->data;
}

int *FindByElement(LinkList *list, Node_ElementType element)
{
    int *p=(int*)malloc(sizeof(int)*(list->len+1));
    if(p==NULL)
    {
        printf("findbyelement malloc error\n");
        return NULL;
    }
    int count=0;
    int k=0;
    Node *TravelPoint=list->head;
    while(TravelPoint->next!=NULL)
    {
        if(TravelPoint->data==element)
            p[k++]=count;
        count++;
        TravelPoint=TravelPoint->next;
    }
    p[k]=-1;
    return p;
}

void SetValueByIndex(LinkList *list, int index, Node_ElementType element)
{
    if(index<0||index>=list->len)
    {
        printf("find invaild place!\n");
        return ;
    }
    Node *TravelPoint=list->head;
    while(index!=0)
    {
        TravelPoint=TravelPoint->next;
        index--;
    }
    TravelPoint->data=element;
}

void SetValueByElement(LinkList *list, Node_ElementType oldvalue, Node_ElementType newvalue)
{
    Node *TravelPoint=list->head;
    while(TravelPoint!=NULL)
    {
        if(TravelPoint->data==oldvalue)
        {
            TravelPoint->data=newvalue;
        }

        TravelPoint=TravelPoint->next;
    }
}

void BubbleSort(LinkList *list)
{
    InsertHead(list,0);
    for(int i=0;i<list->len-2;i++)
    {
        Node *TravelPoint=list->head;
        for(int j=0;j<list->len-i-2;j++)
        {
            if(TravelPoint->next->data>TravelPoint->next->next->data)
            {
                Node *prev=TravelPoint->next;
                Node *next=TravelPoint->next->next;
                prev->next=next->next;
                next->next=prev;
                TravelPoint->next=next;
            }
            TravelPoint=TravelPoint->next;
        }
    }
    RemoveByindex(list,0);
}

void Reserve(LinkList *list)
{
    // int flag=1;
    // Node *TravelPoint=list->head;
    // do
    // {
    //     if(flag==1)
    //     {
    //         list->head=TravelPoint;
    //         TravelPoint=TravelPoint->next;
    //         list->head->next=NULL;
    //         flag=0;
    //     }
    //     else
    //     {
    //     Node *p=list->head;
    //     list->head=TravelPoint;
    //     TravelPoint=TravelPoint->next;
    //     list->head->next=p;
    //     }
    // }while(TravelPoint!=NULL);
    
    Node *prev=NULL;
    Node *cur=list->head;
    Node *next=list->head->next;
    while(next!=NULL)
    {
        cur->next=prev;
        prev=cur;
        cur=next;
        next=cur->next;
    }
    cur->next=prev;
    list->head=cur;
}

Node *Reserve2(Node *node)
{
    Node *tail;
    if(node->next==NULL)
        return node;
    else
    {
        tail=Reserve2(node->next);
        node->next->next=node;
        node->next=NULL;
        return tail;
    }
}

void FreeLinkList(LinkList *list)
{
    while(list->head!=NULL)
    {
        Node *nextnode=list->head->next;
        free(list->head);
        list->head=nextnode;
    }
    list->len=0;
}

void Travel(LinkList *list)
{
    printf("list len:%d\n",list->len);
    Node* TravelPoint=list->head;
    if(TravelPoint==NULL)
    {
        return;
    }
    else
    {
        while(TravelPoint!=NULL)
        {
            printf("%d ",TravelPoint->data);
            TravelPoint=TravelPoint->next;
        }
        printf("\n");
    }
}
